#include<iostream>
#include<assert.h>

using namespace std;

template<class K, class V>
struct AVLTreeNode
{

    pair<K,V> _kv;
    AVLTreeNode<K,V>* _left;      
    AVLTreeNode<K,V>* _right;
    AVLTreeNode<K,V>* _parent;


    int _bf;
  
    AVLTreeNode(const pair<K,V>& kv)
        :_kv(kv)
         ,_left(nullptr)
         ,_right(nullptr)
         ,_parent(nullptr)
         ,_bf(0)
    {}
};  

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K,V> Node;
    
public:

    bool Insert(const pair<K,V>& kv)
    {
        //_root为空
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        
        Node* parent = nullptr;
        Node* cur = _root;
        
        //找到插入的数据的位置
        while(cur)
        {
            if(cur->kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        //插入，并判断插入到parent的左边还是右边
        cur = new Node(kv);
        if(parent->kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        //更新父节点位置
        cur->_parent = parent;
        
        //控制平衡并更新平衡因子
        
        while(parent)
        {
            //插入在左边平衡因子--
            //插入在右边平衡因子++
            if(cur == parent->_right)
                parent->_bf++;
            else
                parent->_bf++;

            //父节点平衡因子为0结束
            if(parent->_bf == 0)
            {
                break;
            }
            //平衡因子为-1或者1，继续向上更新
            else if(parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }

        }

    }

    void RotateR(Node* parent)
    {
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        
        //将cur的右边链接到parent的左边
        parent->_left = curright;
        
        //判断cur的右边是否为空
        //不为空将它链接到父节点的左边
        if(curright)
            curright->_parent = parent;
        
        //记录父节点的父节点
        Node* ppnode = parent->_parent;
        //将父节点连接到cur的右边，以到达降低树的高度
        cur->_right = parent;
        //修改父节点的父节点
        parent->_parent = cur;
        
        //更新ppnode的指向和cur的_parent
        //特殊判断，如果ppnode为空
        //_root 就是 cur
        if(ppnode == nullptr)
        {
            cur->_parent = nullptr;
            _root = cur;
        }
        else
        {
            if(ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }

        //更新平衡因子
        cur->_bf = parent->_bf = 0;


    }

    void RotateL(Node* parent)
    {
        //通过更改parent、cur、curL的指向进行右旋转操作
        //通过右旋转使得AVL的左右高度差绝对值小于等于1
        Node* cur = parent->_right;
        Node* curL = cur->_left;

        //如果curL不为空，将它链接到parent的右边
        if(curL)
            curL->_parent = parent;

        Node* ppnode = parent->_parent;

        if(parent == _root)
        {
            _root == cur;
            cur->_parent = nullptr;
        }
        else 
        {
            if(ppnode->_left == parent)
                ppnode->_left = cur;
            else if(ppnode->_right == parent)

                ppnode->_right = cur;
        }
        cur->_bf = parent->_bf = 0;
    }
private:
    Node* _root;

};
